import java.util.Arrays;
import java.util.Comparator;


public class Solver implements Runnable
{
	
	Data warehouseData;
	private long timeStart;
	String time = "";
	
	public void run()
	{
		
	}
	
	public Solver(Data warehouseData)
	{
		this.warehouseData = warehouseData;
	}
	
	void Solveit()
	{
		//FillWarehouseByCustomerRatio();
		//FillWarehouseByWarehouseCapacity();
		
		FillByAggregateCost();
	}
	
	private void FillByAggregateCost()
	{
		ComputeTotalCost();
		SortByTotalCost();
		//TestTopWarehouse();
		TestAllPossibilities(20);
		

	}

	private void TestAllPossibilities(int nbWarehouse) 
	{
		double bestPrice = 9999999999.0;
		int combinaisonId = 0;
		double cost;
		double nbPossibilities = Math.pow(2, nbWarehouse);
		timeStart = System.currentTimeMillis();
		for(int i=1;i<nbPossibilities;i++)
		{
			double pct = i / nbPossibilities * 100;
			
			OpenSomeWarehouse(i, nbWarehouse);
			OneIteration();
			cost = CalculateCost();
			
			if (cost < bestPrice)
			{
				bestPrice = cost;
				combinaisonId = i;
			}
			
			CalculateTimeLeft(i, nbPossibilities);
			//System.out.println("Solving " + i + " / " + nbPossibilities + ". Best score so far : " + bestPrice);
		}	
		//939937.7375 //50_X
		//
		
		OpenSomeWarehouse(combinaisonId, nbWarehouse);
		OneIteration();
		

	}

	private void CalculateTimeLeft(int iterationDone, double ITERATION_TO_DO) 
	{
		long curTime = System.currentTimeMillis();
		long timeSpent = curTime - timeStart;
		
		double t1 = (double)timeSpent / (double)iterationDone;
		double t2 = t1 * (ITERATION_TO_DO - iterationDone);
		double timeLeft = t2;
		
		String second =""+ (int)((timeLeft / 1000) % 60);
		String minute =""+ (int)((timeLeft / (1000 * 60)) % 60);
		String hour = ""+ (int)((timeLeft / (1000 * 60 * 60)) % 24);

		time  =hour+":"+minute+":"+second;
		
		System.out.println("Time Left : " + time);
		
	}

	private void OneIteration() 
	{
		for(int j = 0; j < warehouseData.customers.length; j++)
		{
			int bestWarehouseId = 0;
			double bestCustomerPrice = 9999999;
			for(int k = 0; k < warehouseData.warehouses.length; k++)
			{
				if (warehouseData.warehouses[k].isOpen && warehouseData.customers[j].cost[k] < bestCustomerPrice)
				{
					bestCustomerPrice = warehouseData.customers[j].cost[k];
					bestWarehouseId = k;
				}
			}
			warehouseData.customers[j].warehouseId = bestWarehouseId;
		}
	}

	private void OpenSomeWarehouse(int warehouseCombination, int nbWarehouse) 
	{
		ResetCustomerWarehouse();
		
		String ans = Integer.toBinaryString(warehouseCombination).toString();
		ans = new StringBuffer(ans).reverse().toString();
		
		for(int j = 0; j < nbWarehouse; j++)
		{
			if (j < ans.length() && ans.charAt(j) == '1')
			{
				warehouseData.warehouses[j].isOpen = true;
			}
		}
	}

	private void TestTopWarehouse()
	{
		double bestPrice = 9999999999.0;
		int combinaisonId = 0;
		
		for(int i = 1; i < 10; i ++)
		{
			double cost = FillSomeOfThem(i);
			if (cost < bestPrice)
			{
				bestPrice = cost;
				combinaisonId = i;
			}
			ResetCustomerWarehouse();
		}
		
		FillSomeOfThem(combinaisonId);
	}

	private void ResetCustomerWarehouse() 
	{
		for(int i = 0; i < warehouseData.customers.length; i++)
		{
			warehouseData.customers[i].warehouseId = -1;
		}
		for(int i = 0; i < warehouseData.warehouses.length; i++)
		{
			warehouseData.warehouses[i].isOpen = false;
		}
	}

	private double FillSomeOfThem(int selectFromTopX) 
	{
		int nbWarehouse = selectFromTopX;
		int nbCustomer = warehouseData.customers.length;
		double cost = 0;
		for(int i = 0; i < nbCustomer; i++)
		{
			int bestWarehouseId = 0;
			double bestPrice = 9999999;
			for(int j = 0; j < nbWarehouse; j++)
			{
				if (warehouseData.customers[i].cost[j] < bestPrice)
				{
					bestPrice = warehouseData.customers[i].cost[j];
					bestWarehouseId = j;
				}
			}
			warehouseData.customers[i].warehouseId = bestWarehouseId;
			warehouseData.warehouses[bestWarehouseId].isOpen = true;
		}
		
		return CalculateCost();
		
	}

	private void SortByTotalCost() 
	{
		Comparator<Warehouse> byCapacity = new WarehouseComparatorCapacity(true);
		Arrays.sort(warehouseData.warehouses, byCapacity);
	}

	private void ComputeTotalCost() 
	{
		int nbClientServed = 0;
		int nbWarehouse = warehouseData.warehouses.length;
		int nbCustomer = warehouseData.customers.length;
		for(int i = 0; i < nbWarehouse; i++)
		{
			warehouseData.warehouses[i].totalCost += warehouseData.warehouses[i].setupCost;
			for(int j = 0; j < nbCustomer; j++)
			{
				warehouseData.warehouses[i].totalCost += warehouseData.customers[j].cost[i];
			}
		}
	}

	private void FillWarehouseByWarehouseCapacity() 
	{
		Comparator<Warehouse> byCapacity = new WarehouseComparatorCapacity(true);
		Arrays.sort(warehouseData.warehouses, byCapacity);
		
		GreedyFillByWarehouseCapacity();
	}
	
	private void GreedyFillByWarehouseCapacity()
	{	
		int nbClientServed = 0;
		int nbWarehouse = warehouseData.warehouses.length;
		int nbCustomer = warehouseData.customers.length;
		for(int i = 0; i < nbWarehouse; i++)
		{
			for(int j = 0; j < nbCustomer; j++)
			{
				if ( warehouseData.customers[j].warehouseId == -1 && warehouseData.warehouses[i].capacity >= warehouseData.customers[j].demand)
				{
					warehouseData.customers[j].warehouseId = i;
					warehouseData.warehouses[i].capacity -= warehouseData.customers[j].demand;
					warehouseData.warehouses[i].isOpen = true;
					nbClientServed++;
					if (warehouseData.warehouses[i].capacity == 0)
					{
						break;
					}
				}
				if (nbClientServed ==nbCustomer) break;
			}
			if (nbClientServed ==nbCustomer) break;
		}
	}
	
	private double CalculateCost()
	{
		double cost = 0;
		for(int i = 0; i < warehouseData.customers.length; i++)
		{
			cost += warehouseData.customers[i].cost[warehouseData.customers[i].warehouseId];
		}
		
		for(int i = 0; i < warehouseData.warehouses.length; i++)
		{
			cost += warehouseData.warehouses[i].setupCost * (warehouseData.warehouses[i].isOpen ? 1 : 0);
		}
		return cost;
	}

	private void FillWarehouseByCustomerRatio() 
	{
		ComputeRatio();
		GreedyFillByCustomerRatio();
		
	}

	private void GreedyFillByCustomerRatio()
	{
		int nbCustomerServed = 0;
		int warehouseOpen = 0;
		int warehouseId = 0;
		while(nbCustomerServed < warehouseData.customers.length)
		{
			for (int i = 0; i < warehouseData.customers.length; i++)
			{
				if ( warehouseData.customers[i].warehouseId == -1 && warehouseData.warehouses[warehouseId].capacity >= warehouseData.customers[i].demand)
				{
					warehouseData.customers[i].warehouseId = warehouseId;
					warehouseData.warehouses[warehouseId].capacity -= warehouseData.customers[i].demand;
					warehouseData.warehouses[warehouseId].isOpen = true;
					nbCustomerServed++;
					
					if (warehouseData.warehouses[warehouseId].capacity == 0)
					{
						break;
					}
				}
			}
			warehouseId++;
			
		}
	}
	
	private void ComputeRatio()
	{
		for(int i = 0; i < warehouseData.warehouses.length; i++)
		{
			for(int j = 0; j < warehouseData.customers.length; j++)
			{
				warehouseData.warehouses[i].ratio += warehouseData.customers[j].cost[i];
			}
			warehouseData.warehouses[i].ratio /= warehouseData.customers.length;
		}
		
		Comparator<Warehouse> byRatio = new WarehouseComparatorRatio(true);
		Arrays.sort(warehouseData.warehouses, byRatio);
	}
}
